package 栈;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * <p>
 * https://leetcode-cn.com/problems/valid-parentheses/
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。
 * 有效字符串需满足：
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 注意空字符串可被认为是有效字符串。
 * </p>
 *
 * @author AJun
 * @since 2020/8/13
 */
public class _20_有效的括号 {

    private static final Map<Character, Character> map = new HashMap<>();

    static  {
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');
    }

    /**
     * {[()]}
     * 这种方法效率太低
     */
    public boolean isValid(String s) {
        while (s.contains("{}") || s.contains("[]") || s.contains("()")) {
            s = s.replace("{}", "");
            s = s.replace("[]", "");
            s = s.replace("()", "");
        }
        return s.length() == 0;
    }

    /**
     * 用栈来实现
     */
    public boolean isValid1(String s) {
        Stack<Character> stack = new Stack<>();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch); // 左括号入栈
            } else {
                // 栈是空的说明没有左括号，非法
                if (stack.isEmpty()) return false;

                // left是左括号，ch 是右括号
                char left = stack.pop();
                if (left == '(' && ch != ')') return false;
                if (left == '[' && ch != ']') return false;
                if (left == '{' && ch != '}') return false;
            }
        }

        // 如果最后栈为空则括号有效
        return stack.isEmpty();
    }

    /**
     * 结合 Map 和 Stack 实现
     */
    public boolean isValid2(String s) {
        Stack<Character> stack = new Stack<>();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            if (map.containsKey(ch)) {
                stack.push(ch); // 左括号入栈
            } else {
                // 栈是空的说明没有左括号，非法
                if (stack.isEmpty()) return false;

                // left是左括号，ch 是右括号
                char left = stack.pop();
                if (ch != map.get(left)) return false;
            }
        }

        // 如果最后栈为空则括号有效
        return stack.isEmpty();
    }

}
